Modern computer systems often comprise a plurality of resources such as processors, memory and I/O controllers. Typically, such resources are coupled to one another by a system bus. While only one device at a time can access the system bus, it is possible that each resource can pose a bus request at any time. Accordingly, it is necessary to provide an arbitration scheme in the computer system which gives all resources fair access to the system bus when deciding which one of several devices that may be requesting access to bus will be granted control of the bus.
There are several known methods for implementing an arbitration scheme in a computer system. One such method is waiting for the bus to become free and then examining all devices that have requested access to the bus. The arbiter then grants the bus to the device according to an arbitration algorithm, e.g., round-robin, priority or least-recently used. Under these approaches, an arbiter may maintain historical information regarding previous bus masters as part of its algorithm.
Maintaining fairness is fundamental to arbiter design. Specifically, there is a need for an arbitration scheme that can provide fair access to a system bus while eliminating the need for maintaining a history of previous bus transactions.